﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution
{
public:
	int rob(vector<int>& nums) {
		int n = nums.size();
		// 两种情况下的最⼤值
		return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
	}
	int rob1(vector<int>& nums, int left, int right) {
		if (left > right) return 0;
		// 1. 创建 dp 表
		// 2. 初始化
		// 3. 填表
		// 4. 返回结果
		int n = nums.size();
		vector<int> f(n);
		auto g = f;
		f[left] = nums[left]; // 初始化
		for (int i = left + 1; i <= right; i++)
		{
			f[i] = g[i - 1] + nums[i];
			g[i] = max(f[i - 1], g[i - 1]);
		}
		
			return max(f[right], g[right]);
	}
};
